1. Field of the Invention
This invention relates generally to computer graphics and more specifically to a system and method for using a point pushing technique to render polygons in environments with changing levels of detail.
2. Description of the Background Art
The resolution of a rendered object generally relates to the number of polygons used to generate that object. A rendered object that contains a greater number of polygons over a given area typically has a higher resolution than an object that contains fewer polygons over the same area.
Graphics engines or graphics software typically implement a technique known as “stripping” when rendering objects. Stripping is a method of generating polygons that enables processors, usually central processing units and graphics processing units, to generate large numbers of polygons while using relatively little processing power. Stripping thereby allows graphics engines or graphics software to render higher resolution objects more quickly and inexpensively. For this reason, producing high resolution graphics for video games and other computer programs and applications that utilize stripping algorithms is simpler and less expensive than producing high resolution graphics for games, programs and applications that do not utilize stripping algorithms.
Stripping generally entails linking polygons in a strip such that a graphics engine or graphics software can generate an additional polygon simply by creating new vertices off one end of the strip and connecting those new vertices to the vertices of the last polygon on that end the strip. The additional polygon and the polygon that was last in the strip share the vertices to which the graphics engine or graphics software connected the new vertices. A triangle is the most commonly used polygon in stripping algorithms because a graphics engine or graphics software can render an additional triangle in a strip by creating only one new vertex and connecting that vertex to each of two vertices of the last triangle in the strip.
When rendering objects, graphics engines or graphics software also typically divide an image screen into different arrays of polygons, sometimes referred to as “meshes.” At any given time, a particular mesh has one or more levels of resolution or levels of detail (LOD) that correspond to the different levels of resolution of the parts of the rendered object(s) represented in the mesh. A higher LOD area of a mesh contains both smaller polygons and a greater number of polygons than a lower LOD area of the mesh contains. The boundary between a higher LOD area of a mesh and a lower LOD area of a mesh is referred to as an “LOD boundary.”
When an LOD boundary intersects one of the polygons in a mesh, the graphics engine or graphics software generates additional polygons on the higher LOD side of the LOD boundary to add detail to that part of the mesh. The area of intersection between the LOD boundary and a side of one of the additional polygons is referred to as a “T-junction.” The result is that only part of the original polygon resides on the lower LOD side of the T-junction (referred to as the “low resolution patch”) and several smaller polygons reside on the higher LOD side of the T-junction (referred to as the “high resolution patch”). Frequently, the low resolution patch and the high resolution patch do not align properly, causing a “crack” in the screen image. A crack is where part of a background image appears in a higher resolution part of a rendered object. This same phenomenon also can occur when a graphics engine or graphics software removes detail from part of a mesh located on a lower LOD side of an LOD boundary.
Several schemes exist that address the T-junction problem described above. These prior art solutions, however, tend to compromise the ability of the graphics engine or graphics software to perform stripping. The consequence is that systems designed to address the T-junction problem lose the efficiencies of stripping and therefore produce lower resolution graphics, and systems that preserve stripping frequently produce graphics that show cracks.